"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, prev, next, child):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child
"""

class Solution(object):
    def flatten(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        node = head
        if not node:
            return None
        stack = []
        while True:
            if node.child:
                if node.next:
                    stack.append(node.next)
                node.next = node.child
                node.child.prev = node
                node.child = None
                node = node.next
            else:
                if node.next:
                    node = node.next
                else:
                    if stack:
                        node.next = stack[-1]
                        stack[-1].prev = node
                        node = node.next
                        stack.pop()
                    else:
                        break

        return head
